package doublePointer;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 *@description 三数之和
 *@author hkfan
 *@version 1.0
 *@create 2025/5/28 10:27
 */
public class LeetCode_15 {

    @Test
    public void test(){
        List<List<Integer>> lists = threeSum(new int[]{-1,0,1,2,-1,-4});
        for (List<Integer> list : lists) {
            for (Integer i : list) {
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {
        //0. 特殊情况
        if (nums.length<3){
            return new ArrayList<>();
        }
        //1. 排序
        Arrays.sort(nums);
        //2. 定义
        List<List<Integer>> lists = new ArrayList<>();

        //3. 循环查找，先固定一个数，再用双指针找其他数
        for (int i = 0; i < nums.length-2; i=next(nums,i,true)) {
            int j=i+1,k=nums.length-1;
            while (j<k){
                if (nums[i]+nums[j]+nums[k]==0){
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    lists.add(list);
                }
                if (nums[i]+nums[j]+nums[k]>=0){
                    k=next(nums,k,false);
                }else {
                    j=next(nums,j,true);
                }
            }
        }
        return lists;
    }

    private int next(int[] nums, int index, boolean flag) {
        int i=0;
        if (flag){
            for (i = index; i < nums.length; i++) {
                if (nums[index]!=nums[i]){
                    return i;
                }
            }
        }else{
            for (i = index; i >= 0; i--) {
                if (nums[index]!=nums[i]){
                    return i;
                }
            }
        }
        return i;
    }


}
